package leetcode.editor.day;

// 641. 设计循环双端队列
// https://leetcode.cn/problems/design-circular-deque/
class DesignCircularDeque {
    //leetcode submit region begin(Prohibit modification and deletion)
    // https://leetcode.cn/problems/design-circular-deque/solution/by-tong-zhu-fdlm/
    // 虚拟头节点
    /*class MyCircularDeque {

        class Node {
            int val;
            Node pre;
            Node next;

            public Node(int val) {
                this.val = val;
                this.pre = null;
                this.next = null;
            }
        }

        int size;
        int capcity;
        Node head, tail;

        public MyCircularDeque(int k) {
            this.capcity = k;
            this.size = 0;
            Node dummy = new Node(0);
            dummy.pre = dummy;
            dummy.next = dummy;
            head = tail = dummy;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }

            Node node = new Node(value);
            insert(head, head.next, node);

            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }

            Node node = new Node(value);
            insert(tail.pre, tail, node);

            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }

            delete(head.next);

            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }

            delete(tail.pre);

            return true;
        }

        public int getFront() {
            return isEmpty() ? -1 : head.next.val;
        }

        public int getRear() {
            return isEmpty() ? -1 : tail.pre.val;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == capcity;
        }

        private void insert(Node pre, Node next, Node node) {
            pre.next = node;
            node.pre = pre;
            node.next = next;
            next.pre = node;

            size++;
        }

        private void delete(Node node) {
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;

            size--;
        }

    }*/

    // 上香链表，无虚拟头节点
    /*class MyCircularDeque {

        class Node {
            int val;
            Node pre;
            Node next;

            public Node(int val) {
                this.val = val;
                this.pre = null;
                this.next = null;
            }
        }

        int size;
        int capcity;
        Node head, tail;

        public MyCircularDeque(int k) {
            this.capcity = k;
            this.size = 0;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }

            Node node = new Node(value);
            if (head == null) {
                head = tail = node;
            } else {
                node.next = head;
                head.pre = node;
                head = node;
            }

            size++;

            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }

            Node node = new Node(value);
            if (tail == null) {
                head = tail = node;
            } else {
                tail.next = node;
                node.pre = tail;
                tail = node;
            }

            size++;

            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }

            if (head.next == null) {
                head = tail = null;
            } else {
                Node next = head.next;
                head.next = null;
                next.pre = null;
                head = next;
            }

            size--;

            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }

            if (tail.pre == null) {
                head = tail = null;
            } else {
                Node pre = tail.pre;
                pre.next = null;
                tail.pre = null;
                tail = pre;
            }

            size--;

            return true;
        }

        public int getFront() {
            return isEmpty() ? -1 : head.next.val;
        }

        public int getRear() {
            return isEmpty() ? -1 : tail.pre.val;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == capcity;
        }
    }*/

    // 数组模拟
    // https://leetcode.cn/problems/design-circular-deque/solution/by-tong-zhu-fdlm/
    class MyCircularDeque {

        int size;
        int capcity;
        int[] arr;
        int front, last;

        public MyCircularDeque(int k) {
            this.capcity = k;
            this.size = 0;
            arr = new int[capcity];
            this.front = this.last = 0;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }

            // 先放值后移动
            arr[front] = value;
            front = index(front + 1);

            size++;

            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }

            // 先移动后放值
            last = index(last - 1);
            arr[last] = value;

            size++;

            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }


            front = index(front - 1);

            size--;

            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }

            last = index(last + 1);

            size--;

            return true;
        }

        public int getFront() {
            return isEmpty() ? -1 : arr[index(front - 1)];
        }

        public int getRear() {
            return isEmpty() ? -1 : arr[index(last)];
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == capcity;
        }

        public int index(int index) {
            return (index + capcity) % capcity;
        }
    }

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
